package Tree;

import org.junit.Test;

import java.util.Arrays;

/**
 * @BelongsProject: SeniorArchitect-LeetCode
 * @BelongsPackage: Tree
 * @Author: zhuangxiaoyan
 * @CreateTime: 2023-10-31  20:55
 * @Description: TODO
 * @Version: 1.0
 */
public class 前序后序构建二叉树 {

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public TreeNode constructFromPrePost(int[] pre, int[] post) {
        if (pre == null || pre.length == 0) {
            return null;
        }
        return dfs(pre, post);
    }

    private TreeNode dfs(int[] pre, int[] post) {
        if (pre == null || pre.length == 0) {
            return null;
        }
        //数组长度为1时，直接返回即可
        if (pre.length == 1) {
            return new TreeNode(pre[0]);
        }
        //根据前序数组的第一个元素，创建根节点
        TreeNode root = new TreeNode(pre[0]);
        int n = pre.length;
        for (int i = 0; i < post.length; ++i) {
            if (pre[1] == post[i]) {
                //根据前序数组第二个元素，确定后序数组左子树范围
                int left_count = i + 1;
                //拆分前序和后序数组，分成四份
                int[] pre_left = Arrays.copyOfRange(pre, 1, left_count + 1);
                int[] pre_right = Arrays.copyOfRange(pre, left_count + 1, n);
                int[] post_left = Arrays.copyOfRange(post, 0, left_count);
                int[] post_right = Arrays.copyOfRange(post, left_count, n - 1);
                //递归执行前序数组左边、后序数组左边
                root.left = dfs(pre_left, post_left);
                //递归执行前序数组右边、后序数组右边
                root.right = dfs(pre_right, post_right);
                break;
            }
        }
        //返回根节点
        return root;
    }


    public TreeNode constructFromPrePost2(int[] pre, int[] post) {
        if (pre == null || pre.length == 0) {
            return null;
        }
        TreeNode root = BuildTree(pre, post);
        return root;
    }

    private TreeNode BuildTree(int[] pre, int[] post) {
        if (pre == null || pre.length == 0) {
            return null;
        }
        if (pre.length == 1) {
            return new TreeNode(pre[0]);
        }
        TreeNode root = new TreeNode(pre[0]);
        int n = post.length;
        int left_count = 0;
        for (int i = 0; i < post.length; i++) {
            if (post[i] == pre[1]) {
                left_count = i + 1;
                int[] pre_left = Arrays.copyOfRange(pre, 1, left_count + 1);
                int[] pre_right = Arrays.copyOfRange(pre, left_count + 1, n);
                int[] post_left = Arrays.copyOfRange(post, 0, left_count);
                int[] post_right = Arrays.copyOfRange(post, left_count, n - 1);
                root.left = BuildTree(pre_left, post_left);
                root.right = BuildTree(pre_right, post_right);
                break;
            }
        }
        return root;
    }

}
